长大后想做什么？做回小孩！

0%

LeetCode——最大子序和

发表于 更新于 分类于 Valine：
本文字数： 361

NO.53 最大子序和 简单

3g44rF.png

思路一：动态规划法 分析dp那就要先分析dp[i]的含义：以第i元素结尾的最大序列和。

初始化：dp[0]以第0号元素结尾的序列只有nums[0]本身，所以dp[0]=nums[0]。

转移方程：dp[i]=Max(dp[i-1]+nums[i],nums[i])，因为dp[i-1]是以i-1为结尾的序列和中的最大值，所以我们想找nums[i]结尾的最大序列和只需要比较”前一个最大序列和+nums[i]”和”nums[i]”。举个例子：

3g4oVJ.md.png

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    int[] dp=new int[nums.length];
    //初始化
    dp[0]=nums[0];
    //填写dp数组同时用max记录当前最大的序列和
    int max=dp[0];
    for (int i = 1; i < nums.length; i++) {
        dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
        max=Math.max(max,dp[i]);
    }
    return max;
}

经过思考不难发现，并不需要开辟一个数组来保存每一个子序和。每次填写只需要关心上一次状态值即可，且每个状态值只需要使用一次。所以我们可以用一个int变量代替dp数组即可：

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    //初始化
    int dp=nums[0];
    //更新当前i结尾的最大序列和同时用max记录最大的序列和
    int max=dp;
    for (int i = 1; i < nums.length; i++) {
        dp=Math.max(nums[i],dp+nums[i]);
        max=Math.max(max,dp);
    }
    return max;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github